package demo1;

/**
 * 哈希桶
 * 使用开散列法解决哈希冲突*/
public class HashBucket {
    //定义节点
    static class Node{
        public int key;
        public int value;
        public Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //定义数组
    public Node[] array;
    //记录元素使用个数，用于计算负载因子
    public int usdSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBucket() {
        this.array = new Node[10];
    }

    /**
     * 在哈希表中插入元素
     * 先使用hash函数计算其下标，再遍历该下标的链表，查看是否存在相同key值
     * 若是存在相同key值，则仅修改其value值并return
     * 若是不存在则尾插
     */
    public boolean put(int key, int value) {
        int index = key%array.length;
        Node cur = array[index];
        Node prev = null;
        while(cur!=null) {
            if(cur.key == key) {
                //若是链表中存在相同key值，仅修改其value值，return false;
                cur.value = value;
                return false;
            }
            prev = cur;
            cur = cur.next;
        }
        //创建prev用于保存cur前一个结点
        //若是cur没找到置为null出循环，此时prev即为链表的尾节点
        if(prev==null) {
            //头插
            array[index] = new Node(key,value);
        } else {
            prev.next = new Node(key,value);
        }
        usdSize++;

        if((usdSize*1.0f/array.length)>DEFAULT_LOAD_FACTOR) {
            //每次插入后计算哈希表的负载因子，若是超过最大负荷比则需要扩容
            resize();
        }
        return true;
    }

    /**
     * 对哈希表进行扩容
     * 要注意的是：不可直接使用Arrays.copyOf进行扩容
     * 因为每个元素都是按照hash函数进行存储的，而hash函数又与数组长度有关
     * 若是需要扩容，则一定要将所有元素重新存放*/
    private void resize() {
        Node[] newArray = new Node[array.length*2];
        //遍历原数组
        for(int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur!=null) {
                Node nextNode = cur.next;
                int newIndex = cur.key% newArray.length;

                //此处使用头插法更为便捷
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;

                cur = nextNode;
            }
        }
        //将数组指向新的数组
        this.array = newArray;
    }

    /**
     * 在哈希表中搜索元素*/
    public int get(int key) {
        int index = key%array.length;
        Node cur = array[index];
        while(cur!=null) {
            if(cur.key==key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
}
